/**
 * 给出一个无重叠，按照区间起始短点排序的区间列表。在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）
 * 示例一: 
 *  输入: intervals = [[1, 3], [6, 9]], newInterval = [2, 5]
 *  输出: [[1, 5], [6, 9]]
 * 示例二:
 *  输入: intervals = [[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], newInterval = [4, 8]
 *  输出: [[1, 2], [3, 10], [12, 16]]
 * 
*/
function insertIntervals (intervals, newInterval) {
    const result = [];
    intervals.push(newInterval);
    // 1. 先按照开始位置给区间排序
    intervals.sort((a, b) => a[0] - b[0]);
    // 2. 判断目标数组的最后一个元素的结束节点是否大于下一个的开始节点，如果大就合并区间，如果小就将下一个元素插入到数组中
    for (let i = 0; i < intervals.length; i++) {
        if (!result.length) {
            result.push(intervals[i]);
        } else {
            const target = result[result.length - 1];
            if (target[1] >= intervals[i][0]) {
                target[1] = Math.max(target[1], intervals[i][1]);
            } else {
                result.push(intervals[i]);
            }
        }
    }
    return result;
}
console.log(insertIntervals([[1, 3], [6, 9]], [2, 5]));
console.log(insertIntervals([[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], [4, 8]));